/*
 * @Author: lei
 * @Description: 堆排序
 * @FilePath: /new/heapsort.cc
 */

#include <iostream>

#include "sort.h"
using namespace std;
/**
 * @description:
 * @param {vector<int>&} v 存储堆的数组
 * @param {int} n 数组（待排序元素）长度
 * @param {int} index 待维护元素的下标
 * @return {void}
 */
void Heapify(vector<int>& v, int n, int index) {
  int largest = index;
  int lson = largest * 2 + 1;
  int rson = largest * 2 + 2;
  // 大顶堆:v[lson或rson] > v[largest]，小顶堆:v[lson或rson] < v[largest]
  // 大顶堆用于升序排序，小顶堆用于降序排序
  if (lson < n && v[lson] > v[largest]) largest = lson;
  if (rson < n && v[rson] > v[largest]) largest = rson;
  if (index != largest) {
    swap(v[index], v[largest]);
    Heapify(v, n, largest);
  }
}

void HeapSort(vector<int>& v) {
  int i;
  int len = v.size();
  // 建堆
  for (int i = len / 2 - 1; i >= 0; i--) Heapify(v, len, i);
  // 堆排序
  for (i = len - 1; i >= 0; i--) {
    swap(v[0], v[i]);
    Heapify(v, i, 0);
  }
}
// int main() {
//   vector<int> v{1, 8, 3, 89, 0, -342, 90, -87, 987, 6};
//   for (auto& t : v) cout << t << " ";
//   cout << endl;
//   HeapSort(v);
//   for (auto& t : v) cout << t << " ";
//   cout << endl;
//   return 0;
// }

// 时间复杂度：初始化建堆的时间复杂度为 O(n)，重建堆的时间复杂度为
// O(nlog⁡n)，所以堆排序总的时间复杂度为 O(nlog⁡n);
// 空间复杂度：O(1)